package day2_linkedlist.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: yuisama
 * @Date: 2021/9/2 15:08
 * @Description:回文链表
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
 * 如果是，返回 true ；否则，返回 false 。
 */
public class Num234 {
    // 方法1,数组法，先遍历一遍链表，将链表元素值存入数组中
    // 再判断数组元素是否是回文即可
//    public boolean isPalindrome(ListNode head) {
//        List<Integer> list = new ArrayList<>();
//        while (head != null) {
//            list.add(head.val);
//            head = head.next;
//        }
//        Object[] arr = list.toArray();
//        int i = 0;
//        int j = arr.length - 1;
//        while (i < j) {
//            // 只要有一个相对位置不相等的元素，一定不回文
//            if (!arr[i].equals(arr[j]))
//                return false;
//            i++;
//            j--;
//        }
//        return true;
//    }

    // 快慢指针法
    // 要想将此问题在O(1)空间复杂度解决，则此问题=反转后半部分链表+找到链表中间节点问题

    public boolean isPalindrome(ListNode head) {
        // 找到中间位置节点
        ListNode middleNode = middleOfList(head);
        ListNode prevList = head;
        // 反转后半链表
        ListNode endMiddleList = reverseList(middleNode);
        while (prevList != null && endMiddleList != null) {
            if (prevList.val != endMiddleList.val)
                return false;
            prevList = prevList.next;
            endMiddleList = endMiddleList.next;
        }
        return true;
    }

    // 反转后半部分链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode temp = head.next;
        ListNode newHead = reverseList(head.next);
        temp.next = head;
        head.next = null;
        return newHead;
    }

    // 找到链表中间节点
    public ListNode middleOfList(ListNode head) {
        ListNode low = head,fast = head;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }
}
